package StruttureDati;

public class StringMatching {
	public static int stringMatchingCancella(String p, String t){
		int m=p.length();
		int n=t.length();
		int[][] d=new int[m][n];
		char[] P=new char[m];
		P=p.toCharArray();
		char[] T=new char[n];
		T=t.toCharArray();
		int i, j, min;
		for(i=1; i<m; i++){d[i][0]=i;}
		for(j=0; j<=n; j++){d[0][j]=0;}
		for(i=1; i<m; i++){
			for(j=1; j<=n; j++){
				min=d[i-1][j-i];
				min=(P[i]==T[j]?min:min+1);
				min=(d[i-1][j]+1<min?d[i-1][j]:min);
				min=(d[i][j-1]+1<min?d[i][j-1]:min);
				d[i][j]=min;
			}
			min=d[m][0];
			i=0;
			for(j=1; j<=n;j++){
				if(d[m][j]<min){min=d[m][j];
				i=j;}
			}
		}
		return i;
	}

}
